package math;

/**
 * @Description 剑指 Offer II 001. 整数除法
 * @Author Firenut
 * @Date 2023-03-26 16:02
 */
public class T001_divide {
    // 如何用加减模拟乘除?
    // 循环减操作,直到|a|<b,返回循环次数
    public int divide(int a, int b) {
        // 考虑被除数为最小值的情况
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            }
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (b == Integer.MIN_VALUE) {
            return a == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (a == 0) {
            return 0;
        }

        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (a > 0) {
            a = -a;
            rev = !rev;
        }
        if (b > 0) {
            b = -b;
            rev = !rev;
        }

        int left = 1, right = Integer.MAX_VALUE, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            int mid = left + ((right - left) >> 1);
            boolean check = quickAdd(b, mid, a);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == Integer.MAX_VALUE) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    // a 和 b 是负数，z 是正数
    // 需要判断 z * b >= a 是否成立 (即 a/b >= z)
    public boolean quickAdd(int b, int z, int a) {
        // a-b 、a-
        int result = 0, add = b;

        while (z != 0) { // z一直在做右移运算直到等于0

            if ((z & 1) != 0) { // 该二进制位对应的数值为1
                // 需要保证 result + add >= a
                if (result < a - add) { // 防止 result + add 溢出
                    return false;
                }
                result += add;
            }

            if (z != 1) {
                // 需要保证 add + add >= a
                if (add < a - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}
